[レポート]キャッシュで踊ろう-Microsoft IIS ハッシュテーブルへの攻撃 – CODE BLUE 2022 #codeblue_jp

CODE BLUE 2022で行われた「キャッシュで踊ろう-Microsoft IIS ハッシュテーブルへの攻撃」というセッションのレポートです。

#CODE BLUE

#CODE BLUE 2022

#セキュリティ

臼田佳祐

2022.10.27

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、臼田です。

今回はCODE BLUE 2022で行われた以下のセッションのレポートです。

ハッシュテーブルは、コンピューターサイエンスにおける最も基本的なデータ構造であり、データを連想的に格納するためのソフトウェアアーキテクチャとして広く応用されている。しかし、その構造上、コリジョン攻撃を受ける可能性が高い。この問題に対処するため、25年前にMicrosoftは独自のDynamic Hashingアルゴリズムを設計し、MicrosoftのWebサーバーであるIISのあらゆる場所に適用して、HTTP Stackからさまざまなデータを提供するようにした。ハッシュテーブルがいたる所にあるように、Microsoftの設計は精査する価値があるのではないか？

われわれは、数カ月にわたるリバース・エンジニアリングを通じてIISの内部に潜入し、Hash Tableの実装とHash Tableアルゴリズムの使用の両方を検証してきた。本研究では、いくつかのタイプの攻撃を提案し、発見した。 ① Microsoftの自己実装アルゴリズムに対して特別に設計されたゼロハッシュ・フラッディング攻撃 ② Hash-Key間の不整合に基づくキャッシュ・ポイズニング攻撃 ③ ハッシュの衝突に基づく異常な認証バイパス攻撃

この講演を理解することで、なぜハッシュテーブルを簡単に不安定にすることができるのか、驚かれることはないだろう。また、IISの内部をどのように調査し、その結果に驚いているのかを知ることができる。これらの結果は、デフォルトでインストールされているIISサーバーを100%のCPUでハングアップさせるだけでなく、細工したHTTPリクエストを通じて任意のHTTPレスポンスを変更することができた。さらに、IDキャッシュを衝突させることで、単一の細工したパスワードで認証要件を回避する方法を紹介する。

Presented by : オレンジ・ツァイ - Orange Tsai

レポート

前回日本に来てからしばらくぶり
コロナ前は年に5-6回日本に来ていた
話す前にちょっとした事例
- スーパーセキュアなログインでは、長いパスワードが必要
- IISでは画面上の8桁の沢山のパスワードすべてが有効である
自己紹介
- Webとアプリの脆弱性リサーチャー
- 様々な肩書がある
概要
- 重要なコンセプト
  - キャッシュについて理解する
- リサーチ
- 脆弱性
  - バイパスを説明
- レコメンド

イントロ

ハッシュテーブル
- データサイエンスの基本的な構造
- 簡単なものはキーバリュー
- 幅広く使われている
- OS / DB / Web Serverなど
- プログラミング言語でも使っている
- よりハイレベルな構造でラップする
  - 配列など
Hash-Flooding Attack
- Hashテーブルを悪用する
- 同じバケットにすべてを入れる
- 攻撃者が予測して悪用する
- 攻撃者が悪意ある記録をいくつか作る
- 最初のレコードは04に書き込める
- 他のものも同じ場所に書き込める
- そうするとテーブルが単一のリストになる
- O(n2)となる
- パフォーマンスがひどい
IISはハッシュテーブルが大好き
- 幅広く使っている
- HTTPヘッダ、サーバー変数、キャッシュなどを保存する
- 幅広く使われている
- TREE_HASH_TABLE
  - 最もよくある共通のハッシュテーブル
  - Linked-Listにする
  - このハッシュ関数の使い方はあとから
- LKRHash Table
  - 拡張可能
  - 同時並行のものを導入する
  - LKRは作成者の頭文字
  - Linear Hashingを活用
  - 作成者の一部はIISのチームにも所属している

リサーチ

バグを見つけるだけでなく仕様に注目している
キャッシュのメカニズムがメインターゲット
自身をOSSを使って設計していない
メモリの破損やロジックバグを探していく
CVE-2006-3017にフォーカス
- PHPのインプリ
- 攻撃者は恣意的なものでunset()できる
Hash-Floodingも見ている
ほとんどは解決済み
インプリに注目していく
LKRHashは持ち運びしやすい
自身のテーブル関連の機能を初期化できる
バグを見つける機会を広げる
どのようにコリジョンが起きたときに選べるのか
関係性を考える
- リクエストを受けたときにHTTP.SYSがあつかい、ディスパッチする
- アクティブなものがなければWASが新しいプロセスを起動する
- Workerが動く
- WorkerからIIS Modulesを読み込む
IISはデフォルトで様々なモジュールを読み込む
- グローバルキャッシュプロバイダーでいくつか管理される
  - 静的ファイル
  - ログオントークン
  - など
- すべてロードされるとライフサイクルを入力
リクエストライフサイクル
- キャッシュクリーンなどにサブスクライブする
- リクエストライフサイクルだけでなくグローバルキャッシュプロバイダーもターゲット

脆弱性

今回は2つ紹介
FloodingとBypass
どのように最大化するか
Hash Flooding Attack
- すべてのハッシュが影響をうける
- 脆弱であるから侵入できるわけではない
- いくつか乗り越えないといけない
UriCacheModule
- 良いターゲットに見えた
- TREE_HASH_TABLEを使っていた
- アクセス可能なTREE_HASH_TABLEは聞こえは良い
- ランダム挿入とコリジョンがある挿入に違いがある
- 35kと75kのジッターがおかしい
- 通常は線形であるはず
- なぜなのか
答えはリハッシュ
- Insertのコードを見る
- 重複がないことを確認する
- RehashTableIfNeededという関数が実行される
- しきい値はPrimeから選ばれる
- 関数は表を拡大し再マッピングする
- なのでなめらかに増加しない
高価なRehashを使う前に質問がある
- いくつコントロールできるか
- コリジョンはどうやるか
- 制御できるのはURLのみ
- すべてを大文字にしてハッシュ計算する
- CalcHash関数
- 101でかけて足す
- ハッシュ関数はこれでいいのか？
- No
- DJBハッシュを変形したもの
- 衝突可能であることが証明されている
- Equivalent Substrings
- 2つを組み合わせて違う値で同じハッシュを作れる
- STRINGを繰り返せるので簡単に実現できる
- しかしまだ弱い
- 1つのリクエストで1つのレコードしか加えられない
- 35k送らないといけないので遅い
- しかもCache Scavengerがいる
- 利用していない記録を30秒ごとに消去される
これを乗り越えるためにimplementationに移る
- この攻撃を助けられる挙動
- キーを再帰的にスキャンする
- 各サブディレクトリは新しい記録として扱われるので複数Insertで扱う
- どうやってハッシュをサブディレクトリすべて衝突させるか
- 0にすれば簡単
- 0 Hashのセットを作って10倍の攻撃が可能になる
結果
- サーバーを止めるのに30リクエスト/secで実現
- デフォルトで影響したのでバウンティを獲得
- youtubeにデモがある
認証バイパス
- なぜ沢山のパスワードでバイパスできるのか
- Logonはコストの掛かるオペレーション
- パフォーマンスを落とさないようにすべてをキャッシュしている
- LKRHashをつかう
- 15分毎消去している
LKRHash Table
- 様々な関数がある
- fnCalcKeyHash
- fnEqualKeys
  - どれが正しいのかを確認する
  - 両方のメソッドとユーザーネームを2回チェック
  - なぜ2回？
  - 当初はパスワードをチェックするところで間違えて実装したのでは
  - コードをコピペしたので
- これで問題が生まれる
- Usernameだけでチェックするようになる
別のユーザーのログイントークンをランダムパスワードで再利用できる
- 前提条件がいくつかある
  - 1/2^32の確率
  - 攻撃が成功する前にログインが成功して15分以内であること
- これでこのバグは価値がなくなる
このバグをより深刻なものにするために3つの方法を考えた
- 衝突の可能性を増やす
- ユーザーインタラクションなしで利用する
  - あまりかっこうよくないから
- 15分の制限時間を突破する
衝突
- 40億分の1はとんでもない
- LCGで小さくできる
- 辞書を事前に計算してキャッシュに入っていないパスワードを減らす
- KeySpaceを減らして成功率を13%増やす
Connect As
- 通常はVirtual Hostingで使っている
- これを再利用する
- Windows Serverを1,800のログインを秒間で処理できる
- ガチャでSSRを出すより確率を高くできた
- 5日続ければ20%
- 24日で100%に到達する
- パスワードを5日で得ることができた
時間
- 考えはシンプル
- バックグラウンドデーモンを見ることが一般的
- クレデンシャルがCRONにアタッチされている
- 15分以内にアクセスしていればなくならない
- ある
- Exchangeサーバーの話
- Active Monitoring Service
  - デフォルトで有効化
  - すべてのサービスを確認
  - 10分毎
- クレデンシャルが永遠にキャッシュされる
- 試したいだけ試すことができる
- OWAのログインに利用することができる
- メールボックスを持っている